package codingforgreat.lchot150;

public class Lc329 {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int res = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                res = Math.max(res, process1(matrix, i, j,dp));
            }
        }
        return res;
    }
    public int process1(int[][] m, int i, int j,int[][] dp){
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        int up = i > 0 && m[i][j] < m[i - 1][j] ? process1(m, i - 1, j,dp) : 0;
        int down = i < m.length - 1 && m[i][j] < m[i + 1][j] ? process1(m, i + 1,j,dp):0;
        int left =  j > 0 && m[i][j] < m[i][j - 1] ? process1(m, i, j - 1,dp) : 0;
        int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process1(m, i, j + 1,dp) : 0;
        int res = Math.max(up, Math.max(down, Math.max(left, right))) + 1;
        dp[i][j] = res;
        return res;
    }


}
